package com.ryujung.dfs_backtracking;
/*
 * @lc app=leetcode.cn id=200 lang=java
 *
 * [200] 岛屿数量
 */


// @lc code=start
class Solution {
    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int result = 0;
        int N = grid.length;
        int M = grid[0].length;
        boolean[][] isVisited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == '1' && !isVisited[i][j]) {
                    dfs(grid, N, M, i, j, isVisited);
                    result++;
                }
            }
        }
        return result;
    }

    private static void dfs(char[][] grid, int N, int M, int i, int j, boolean[][] isVisited) {
        if (i < 0 || j < 0 || i >= N || j >= M) {
            return;
        }

        int[][] moves = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        for (int[] move : moves) {
            int n = i + move[0];
            int m = j + move[1];

            if (n >= 0 && n < N && m >= 0 && m < M && grid[n][m] == '1' && !isVisited[n][m]) {
                isVisited[n][m] = true;
                dfs(grid, N, M, n, m, isVisited);
            }
        }
        isVisited[i][j] = true;
    }

    public static void main(String[] args) {
        char[][] arr = new char[5][7];
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                arr[i][j] = (Math.random() < 0.5) ? '0' : '1';
            }
        }
        for(char[] chs : arr) {
            for(char ch : chs) {
                System.out.print(ch + ", ");
            }
            System.out.println();
        }
        System.out.println(numIslands(arr));
    }
}
// @lc code=end
